{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Town Judge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findJudge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到小镇的法官"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>小镇里有 <code>n</code> 个人，按从 <code>1</code> 到 <code>n</code> 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。</p>\n",
    "\n",
    "<p>如果小镇法官真的存在，那么：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>小镇法官不会信任任何人。</li>\n",
    "\t<li>每个人（除了小镇法官）都信任这位小镇法官。</li>\n",
    "\t<li>只有一个人同时满足属性 <strong>1</strong> 和属性 <strong>2</strong> 。</li>\n",
    "</ol>\n",
    "\n",
    "<p>给你一个数组 <code>trust</code> ，其中 <code>trust[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示编号为 <code>a<sub>i</sub></code> 的人信任编号为 <code>b<sub>i</sub></code> 的人。</p>\n",
    "\n",
    "<p>如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, trust = [[1,2]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, trust = [[1,3],[2,3]]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, trust = [[1,3],[2,3],[3,1]]\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= trust.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>trust[i].length == 2</code></li>\n",
    "\t<li><code>trust</code> 中的所有<code>trust[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> <strong>互不相同</strong></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-town-judge](https://leetcode.cn/problems/find-the-town-judge/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-town-judge](https://leetcode.cn/problems/find-the-town-judge/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[[1,2]]', '3\\n[[1,3],[2,3]]', '3\\n[[1,3],[2,3],[3,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        \n",
    "        in_degree = [0]*N\n",
    "        out_degree = [0]*N\n",
    "        \n",
    "        for a,b in trust:\n",
    "            out_degree[a-1]+=1\n",
    "            in_degree[b-1]+=1\n",
    "            \n",
    "        for i in range(1,N+1):\n",
    "            if in_degree[i-1]==N-1 and out_degree[i-1]==0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: 'int', trust: 'List[List[int]]') -> 'int':\n",
    "        trust.sort()\n",
    "        trust0 = []\n",
    "        trust_num = -1\n",
    "        total = 0\n",
    "        for i in trust:\n",
    "            trust0.append(i[0])\n",
    "        for num in range(1,N+1):\n",
    "            if num not in trust0:\n",
    "                trust_num = num\n",
    "                break\n",
    "        if trust_num == -1:\n",
    "            return -1\n",
    "        for i in trust:\n",
    "            if i[1] == trust_num:\n",
    "                total += 1\n",
    "        if total == N-1:\n",
    "            return trust_num\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: 'int', trust: 'List[List[int]]') -> 'int':\n",
    "        s = set(list(range(1,N+1)))\n",
    "        d = {}\n",
    "        for pa,pb in trust:\n",
    "            if pa in s:s.remove(pa)\n",
    "            d[pb]=d.get(pb,0)+1\n",
    "        res = []\n",
    "        for p in s:\n",
    "            if d.get(p,0)==N-1:\n",
    "                res.append(p)\n",
    "        if len(res)==1:\n",
    "            return res[0]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        if N==1:\n",
    "            return 1\n",
    "        ind,oud=[0 for _ in range(N+1)],[0 for _ in range(N+1)]\n",
    "        for i in range(len(trust)):\n",
    "            ind[trust[i][1]]+=1\n",
    "            oud[trust[i][0]]+=1\n",
    "        for i in range(1,N+1):\n",
    "            if ind[i]==N-1 and oud[i]==0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findJudge(self, N: 'int', trust: 'List[List[int]]') -> 'int':\n",
    "        if not trust:\n",
    "            return 1;\n",
    "        trust_map=defaultdict(set)\n",
    "        trust_set=set()\n",
    "        for it in trust:\n",
    "            trust_map[it[1]].add(it[0])\n",
    "            trust_set.add(it[0])\n",
    "            \n",
    "        for key,val in trust_map.items():\n",
    "            if len(val)==N-1 and key not in trust_set:\n",
    "                return key\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: 'int', trust: 'List[List[int]]') -> 'int':\n",
    "        if N==1:\n",
    "            return 1\n",
    "        d =dict()\n",
    "        ps  = set()\n",
    "        for p,n in trust:\n",
    "            ps.add(p)\n",
    "            if n not in d:\n",
    "                d[n] = set()\n",
    "            d[n].add(p)\n",
    "            \n",
    "        for k in d.keys():\n",
    "            if len(d[k]) == N-1 and k not in ps:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._id = set()\n",
    "        self.bxr = set()\n",
    "        self.all_info = dict()\n",
    "\n",
    "    def findJudge(self, N: 'int', trust: 'List[List[int]]') -> 'int':\n",
    "\n",
    "        if not trust:\n",
    "\n",
    "            return 1\n",
    "\n",
    "        for tmp in trust:\n",
    "            a, b = tmp\n",
    "            if self.all_info.get(b):\n",
    "                self.all_info[b].add(a)\n",
    "            else:\n",
    "                self.all_info[b] = {a, }\n",
    "            self.bxr.add(a)\n",
    "            self._id.add(b)\n",
    "\n",
    "        if len(self._id) and len(self.bxr | self._id) == N:\n",
    "\n",
    "            for j in self.bxr & self._id:\n",
    "                self._id.remove(j)\n",
    "\n",
    "            if self._id:\n",
    "                for ii in self._id:\n",
    "                    self.all_info[ii].add(ii)\n",
    "                    if len(self.all_info[ii]) == N:\n",
    "                        return ii\n",
    "                    else:\n",
    "                        return -1\n",
    "            else:\n",
    "                return -1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: 'int', trust: 'List[List[int]]') -> 'int':\n",
    "        if N==1 and trust==[]:\n",
    "            return 1\n",
    "        l1=[]\n",
    "        l2=[]\n",
    "        for t in trust:\n",
    "            l1.append(t[0])\n",
    "            l2.append(t[1])\n",
    "        s2=set(l2)\n",
    "        for s in s2:\n",
    "            if l2.count(s)==N-1 and (s not in l1):\n",
    "                return s\n",
    "        return -1\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: 'int', trust: 'List[List[int]]') -> 'int':\n",
    "\n",
    "        init_N = [True for _ in range(N)]\n",
    "        init_trust = [set() for _ in range(N)]\n",
    "\n",
    "        for each in trust:\n",
    "            init_N[each[0]-1] = False\n",
    "            init_trust[each[1]-1].add(each[0]-1)\n",
    "        print(init_N, init_trust)\n",
    "        for index, each in enumerate(init_N):\n",
    "            if each == True:\n",
    "                if len(init_trust[index]) == N-1:\n",
    "                    return index+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: 'int', trust: 'List[List[int]]') -> 'int':\n",
    "        if not trust :\n",
    "            a,b=[],[]\n",
    "            if N==1:\n",
    "                return 1\n",
    "        else:\n",
    "            a, b = zip(*trust)\n",
    "\n",
    "        dic = {}\n",
    "        for k, v in trust:\n",
    "            # print(k,v)\n",
    "            mask = dic.get(v) or None\n",
    "            if not  mask:\n",
    "                dic[v] = [k]\n",
    "            else:\n",
    "                dic[v].append(k)\n",
    "\n",
    "        for item in sorted(dic,key=lambda x:-len(dic[x])):\n",
    "            # print(item,dic[item])\n",
    "            if len(dic[item])==N-1 and item not in set(a):\n",
    "                # print(item)\n",
    "                return item\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        arr=[[0,0] for i in range(N+1)]\n",
    "        for i in trust:\n",
    "            arr[i[0]][0]+=1\n",
    "            arr[i[1]][1]+=1\n",
    "        for i in range(1,N+1):\n",
    "            if arr[i][0]==0 and arr[i][1]==N-1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        count = [0]*(N+1)\n",
    "        for i,j in trust:\n",
    "            count[i] -=1\n",
    "            count[j] +=1\n",
    "        for i in range(1,N+1):\n",
    "            if count[i] == N-1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        a=[]\n",
    "        b={}\n",
    "        for i in trust:\n",
    "            a.append(i[0])\n",
    "            b[i[1]]=b.get(i[1],0)+1\n",
    "        a=[i for i in range(1,N+1) if i not in set(a) and b.get(i,0)==N-1]\n",
    "        return -1 if len(a)!=1 else a[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        indegree = [0] * (N + 1)\n",
    "        outdegree = [0] * (N + 1)\n",
    "        res = list()\n",
    "        for pair in trust:\n",
    "            outdegree[pair[0]] += 1\n",
    "            indegree[pair[1]] += 1\n",
    "        for i in range(1, N + 1):\n",
    "            if outdegree[i] == 0 and indegree[i] == N - 1:\n",
    "                res.append(i)\n",
    "        return res[0] if len(res) == 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        a = defaultdict(int)\n",
    "        for i, _ in trust:\n",
    "            a[i] += 1\n",
    "        b = defaultdict(int)\n",
    "        for _, i in trust:\n",
    "            b[i] += 1\n",
    "        for i in range(1, N+1):\n",
    "            if a[i] == 0 and b[i] == N-1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        # N-1 trust a same person\n",
    "        # 1 person dont trust N-1 persons\n",
    "        if len(trust) <= 0:\n",
    "            if N==1:\n",
    "                return N\n",
    "            else:\n",
    "                return -1\n",
    "        people = {}\n",
    "        for item in trust:\n",
    "            if item[1] not in people:\n",
    "                people[item[1]] = []\n",
    "            if item[0] not in people[item[1]]:\n",
    "                people[item[1]].append(item[0])\n",
    "        values = []\n",
    "        for v in list(people.values()):\n",
    "            values += v\n",
    "        for key in people:\n",
    "            if key not in people[key] and len(people[key]) == N-1 and key not in values:\n",
    "                return key\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        trustset = set()\n",
    "        for x, y in trust:\n",
    "            trustset.add((x, y))\n",
    "\n",
    "\n",
    "        def istrust(i, j):\n",
    "            return (i,j) in trustset\n",
    "\n",
    "        judge = 1\n",
    "\n",
    "        for i in range(2, N + 1):\n",
    "            if istrust(judge, i):\n",
    "                judge = i\n",
    "\n",
    "        for i in range(1, N + 1):\n",
    "            if i!= judge and (not istrust(i, judge) or istrust(judge, i)):\n",
    "                return -1\n",
    "\n",
    "        return judge\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\r\n",
    "        if n == 1:\r\n",
    "            return 1\r\n",
    "        ret_list = [0] * (n + 1)\r\n",
    "        for i in trust:\r\n",
    "            ret_list[i[0]] -= 1\r\n",
    "            ret_list[i[1]] += 1\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            if ret_list[i] == n - 1:\r\n",
    "                return i\r\n",
    "        return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "\n",
    "        #图\n",
    "\n",
    "        trusted=set(range(1,n+1))\n",
    "        votes=collections.defaultdict(int)\n",
    "\n",
    "        for a,b in trust:\n",
    "            trusted.discard(a)\n",
    "            votes[b]+=1\n",
    "\n",
    "        if len(trusted)==1:\n",
    "            p=trusted.pop()\n",
    "            if votes[p]==n-1:\n",
    "                return p\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        in_count = [0] * (n+1)\n",
    "        out_count = [0] * (n+1)\n",
    "        for person in trust:\n",
    "            in_count[person[1]] += 1\n",
    "            out_count[person[0]] += 1\n",
    "        for i in range(1, n+1):\n",
    "            if in_count[i] == n-1 and out_count[i] == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        s = size = n + 1\n",
    "        w = [1] * s\n",
    "        for i, j in trust:\n",
    "            w[i] -= 1\n",
    "            w[j] += 1\n",
    "\n",
    "        for k in range(1, s):\n",
    "            if w[k] == n:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        # 1.取出被信任且不相信他人的人，遍历，如果被相信人的数量=n-1，返回被信任的人，否则返回-1\n",
    "        # if len(trust) == 0 and n ==1:\n",
    "        #     return 1\n",
    "        # set_list1 = list(set(i[1] for i in trust))\n",
    "        # set_list0 = set(i[0] for i in trust)\n",
    "        # for i in set_list0:\n",
    "        #     if i in set_list1:\n",
    "        #         set_list1.remove(i)\n",
    "        # if len(set_list1) > 0:\n",
    "        #     for i in set_list1:\n",
    "        #         sum = 0\n",
    "        #         for j in trust:\n",
    "        #             if j[1] == i:\n",
    "        #                 sum += 1\n",
    "        #         if sum == n-1:\n",
    "        #             return i\n",
    "        #     else:\n",
    "        #         return -1\n",
    "        # else:\n",
    "        #     return -1\n",
    "        # 2.方法1集合优化\n",
    "        # if len(trust) == 0 and n ==1:\n",
    "        #     return 1\n",
    "        # list1 = set(i for i in range(1,n+1))\n",
    "        # set_list0 = set(i[0] for i in trust)\n",
    "        # list_0 = list1 - (list1 & set_list0)\n",
    "        # # print(list_0)\n",
    "        # if len(list_0) > 0:\n",
    "        #     for i in list_0:\n",
    "        #         sum = 0\n",
    "        #         for j in trust:\n",
    "        #             if j[1] == i:\n",
    "        #                 sum += 1\n",
    "        #         if sum == n-1:\n",
    "        #             return i\n",
    "        #     else:\n",
    "        #         return -1\n",
    "        # else:\n",
    "        #     return -1\n",
    "        # a = [0 for x in range(n+1)] #相信你的人\n",
    "        # b = [0 for x in range(n+1)] #你相信的人\n",
    "\n",
    "        # for num in trust:\n",
    "        #     a[num[1]] += 1   #存储的为相信他的人\n",
    "        #     b[num[0]] += 1\n",
    "\n",
    "        # for i,num in enumerate(a):\n",
    "        #     if(i!=0 and num == n-1): #所有人都相信法官\n",
    "        #         if(b[i] == 0): #法官不相信任何人\n",
    "        #             return i\n",
    "        # return -1\n",
    "        list1 = set([i[0] for i in trust])\n",
    "        list2 = set([i for i in range(1, n + 1)])\n",
    "        pop = list2 - list1\n",
    "        if len(pop) == 1:\n",
    "            num = 0\n",
    "            for i in trust:\n",
    "                if i[1] == list(pop)[0]:\n",
    "                    num += 1\n",
    "            if num == n - 1:\n",
    "                return list(pop)[0]\n",
    "            else:\n",
    "                return -1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        if not trust and n == 1:\n",
    "            return 1\n",
    "\n",
    "        dict_be_trust = collections.defaultdict(int)\n",
    "        trust_list = set()\n",
    "        for v in trust:\n",
    "            dict_be_trust[v[1]] += 1\n",
    "            trust_list.add(v[0])\n",
    "\n",
    "        for k, v in dict_be_trust.items():\n",
    "            if v == (n-1) and k not in trust_list:\n",
    "                return k\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        trust_pair = [[0, 0] for i in range(n)]\n",
    "        for t in trust:\n",
    "            # trust\n",
    "            trust_pair[t[0]-1][0] += 1\n",
    "            # be trusted\n",
    "            trust_pair[t[1]-1][1] += 1\n",
    "        if [0, n - 1] in trust_pair:\n",
    "            return trust_pair.index([0, n - 1]) + 1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        judge = [True]*n\n",
    "        dic = {}\n",
    "        for i, j in trust:\n",
    "            # print(dic, judge)\n",
    "            dic[j]  = dic.get(j, 0)+1\n",
    "            judge[i-1] = False\n",
    "        for i in range(n):\n",
    "            if judge[i] and dic.get(i+1,0) == n-1:\n",
    "                return i+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        m = len(trust)\n",
    "        # trustSet = set(trust)        \n",
    "        judge = -1\n",
    "        for i in range(1,n+1):\n",
    "            q1 = 0\n",
    "            q2 = 1\n",
    "            for j in range(m):\n",
    "                if (i != trust[j][0]):\n",
    "                    q1 += 1\n",
    "            for k in range(1,n+1):\n",
    "                if k == i:\n",
    "                    continue\n",
    "                if [k, i] not in trust:\n",
    "                    # continue\n",
    "                    q2 = 0\n",
    "                    break\n",
    "                # else:\n",
    "                #     continue\n",
    "            if (q1 == m) and (q2 == 1):\n",
    "                judge = i\n",
    "        return judge\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        s,l=set(),[0]*n\n",
    "        for a,b in trust:\n",
    "            s.add(a)\n",
    "            l[b-1]+=1\n",
    "\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if i not in s and l[i-1]==n-1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        in_degree = [0] * (n + 1)\n",
    "        out_degree = [0] * (n + 1)\n",
    "        for a,b in trust:\n",
    "            in_degree[b] += 1\n",
    "            out_degree[a] += 1\n",
    "        for i in range(1,n + 1):\n",
    "            if in_degree[i] == n - 1 and out_degree[i] == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, n: int, trust: List[List[int]]) -> int:\n",
    "        inDegrees = Counter(y for _, y in trust)\n",
    "        outDegrees = Counter(x for x, _ in trust)\n",
    "        return next((i for i in range(1, n + 1) if inDegrees[i] == n - 1 and outDegrees[i] == 0), -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findJudge(self, N: int, trust: List[List[int]]) -> int:\n",
    "        if not trust:\n",
    "            return(1) if N == 1 else -1\n",
    "        judge = {}\n",
    "        for i in trust:\n",
    "            if i[1] in judge:\n",
    "                judge[i[1]].append(i[0])\n",
    "            else:\n",
    "                judge[i[1]] = [i[0]]\n",
    "        judge_person = -1\n",
    "        num = 0\n",
    "        for i in judge:\n",
    "            if len(judge[i]) == N-1:\n",
    "                judge_person = i\n",
    "                num += 1\n",
    "        if num == 1:\n",
    "            for i in judge:\n",
    "                if judge_person not in judge[i]:\n",
    "                    pass\n",
    "                else:\n",
    "                    return(-1)\n",
    "            return(judge_person)\n",
    "        else:\n",
    "            return(-1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
